package leetcode_141_160;

import utils.ListNode;

import java.util.Stack;

public class getIntersectionNode_160 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /**
         * 想法是用栈保存两个链表的所有节点
         * 然后弹出节点进行比较
         * 3ms
         */
        Stack<ListNode>stackA=new Stack<>();
        Stack<ListNode>stackB=new Stack<>();
        ListNode rootA=headA;
        ListNode rootB=headB;
        while(rootA!=null){
            stackA.add(rootA);
            rootA=rootA.next;
        }
        while(rootB!=null){
            stackB.add(rootB);
            rootB=rootB.next;
        }
        ListNode ans=null;
        while (stackA.size() > 0 && stackB.size() > 0) {
            ListNode A=stackA.pop();
            if (A != stackB.pop())
                return ans;
            else
                ans=A;
        }
        return ans;
    }
    /**
     * 高解的思路，神中神
     * 1ms
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        /**
         *     pA走过的路径为A链+B链
         *     pB走过的路径为B链+A链
         *     pA和pB走过的长度都相同，都是A链和B链的长度之和，相当于将两条链从尾端对齐
         *     如果相交，则会提前在相交点相遇，如果没有相交点，则会在最后相遇。
         *     pA:1->2->3->4->5->6->null->9->5->6->null
         *     pB:9->5->6->null->1->2->3->4->5->6->null
         */
        ListNode A = headA, B = headB;
        while(A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }


}
